package BinarySearch.Medium;

public class LC0033 {
    public int search(int[] nums, int target) {
        return search(nums, target, 0, nums.length);
    }

    /**
     * 我的解法。这道题的逻辑较为复杂，关键是利用nums[mid]和nums[left]（或nums[right]）的大小关系判断旋转点是在mid左侧还是右侧。
     * 之后需要根据nums[mid]、nums[left]、nums[right]与target的关系判断向哪一侧搜寻。注意mid的一侧是有序数组，一侧是旋转数组。
     * 当落在有序数组一侧时，可以使用普通的二分查找；当落在旋转数组一侧时，可以进行递归。
     * 这道题要求设计logN复杂度的算法。受到二分查找的启发，如果一个算法能够每次排除一半的元素，那么这个算法复杂度就是logN。
     */
    private int search(int[] nums, int target, int left, int right) {
        // 特殊情形处理
        int n = right - left;
        if (n < 3) {
            for (int i = 0; i < n; i++) if (nums[i + left] == target) return i + left;
            return -1;
        }

        int mid = (int) (((long) left + right) / 2);
        if (nums[mid] == target) return mid;

        if (nums[mid] > nums[left]) { // 旋转位置在右侧，或mid为原数组末尾
            if (nums[mid] > target) {
                if (nums[left] <= target) { // 落在左侧有序区域，普通二分查找
                    return binarySearch(nums, target, left, mid);
                }
                else if (nums[right - 1] < target) { // 位于左右边界的值之间，表示无法找到
                    return -1;
                }
                else { // 位于右侧旋转数组，向右侧递归
                    return search(nums, target, mid + 1, right);
                }
            }
            else { // nums[mid] < target，向右侧搜索（左侧是有序数组）
                if (nums[mid + 1] < nums[mid]) return -1; // 到达原数组末尾
                return search(nums, target, mid + 1, right);
            }
        }
        else { // nums[mid] < nums[left]，旋转位置在左侧，或者mid为原数组起始位置
            if (nums[mid] < target) {
                if (nums[right - 1] >= target) return binarySearch(nums, target, mid + 1, right); // 普通二分查找
                else if (nums[left] > target) return -1; // 位于左右边界的值之间，表示无法找到
                else return search(nums, target, left, mid);
            }
            else { // nums[mid] > target，向左侧搜索（右侧是有序数组）
                if (nums[mid - 1] > nums[mid]) return -1; // 到达原数组起始位置
                return search(nums, target, left, mid);
            }
        }

    }

    /**
     * 双二分解法，参考了@宫水三叶的解法。“「二分」的本质是两段性，并非单调性。只要一段满足某个性质，另外一段不满足某个性质，就可以用「二分」。”
     * 这句话和search(int[], int, int, int)方法上写的注解有相同的思想，即如果一次可以排除一半的元素，那么事实上使用的就是二分。
     * 相比我的题解，宫水题解的主要改进是使用二分查找来确定旋转点的位置。不考虑特殊情况，如果nums[0]>nums[mid]，那么旋转位置就在0和mid之间；
     * 如果nums[0]<nums[mid]，那么旋转位置就在mid右侧。
     * 事实上，我的解法也利用了这一性质，但是没有想到可以直接用二分查找来找出旋转位置。
     */
    public static int searchByDualBinarySearch(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return -1;
        if (n == 1) return nums[0] == target ? 0 : -1;

        // 第一次二分：找到原始数组的起始
        int left = 0, right = n, mid;
        int originalHead = 0;
        while (left < right) {
            mid = (int) (((long) left + right) / 2);
            if (mid > 0 && nums[mid - 1] > nums[mid]) {
                originalHead = mid;
                break;
            }
            else if (mid == 0) {
                originalHead = 0;
                break;
            }
            if (nums[0] > nums[mid]) right = mid;
            else if (nums[0] < nums[mid]) left = mid + 1;
        }

        // 第二次二分：判断target在哪一段有序子数组中，使用常规二分
        if (originalHead == 0) return binarySearch(nums, target, 0, n);
        if (target > nums[n - 1] && target < nums[0]) return -1;
        if (target >= nums[0] && target <= nums[originalHead - 1])
            return binarySearch(nums, target, 0, originalHead);
        else return binarySearch(nums, target, originalHead, n);
    }

    private static int binarySearch(int[] nums, int target, int left, int right) {
        if (left >= right) return -1;
        while (left < right) {
            int mid = (int) (((long) left + right) / 2);
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1};
        System.out.println(searchByDualBinarySearch(nums, 0));
    }
}
